#define _CRT_SECURE_NO_WARNINGS

#include "Sort.h"
#include "Stack.h"

void TestInsertSort()
{
	int a[] = { 4,7,1,9,5,8,3 };
	int sz = sizeof(a) / sizeof(a[0]);
	PrintArray(a, sz);
	InsertSort(a, sz);
	PrintArray(a, sz);
}

void TestShellSort()
{
	int a[] = { 4,7,1,9,5,8,3 };
	int sz = sizeof(a) / sizeof(a[0]);
	PrintArray(a, sz);
	ShellSort(a, sz);
	PrintArray(a, sz);
}

void TestBubbleSort()
{
	int a[] = { 4,7,1,9,5,8,3 };
	int sz = sizeof(a) / sizeof(a[0]);
	PrintArray(a, sz);
	BubbleSort(a, sz);
	PrintArray(a, sz);
}

//void TestSelectSort()
//{
//	int a[] = { 4,7,1,9,5,8,3 };
//	int sz = sizeof(a) / sizeof(a[0]);
//	PrintArray(a, sz);
//	SelectSort(a, sz);
//	PrintArray(a, sz);
//}

void TestSelectSort()
{
	int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
	int sz = sizeof(a) / sizeof(a[0]);
	PrintArray(a, sz);
	SelectSort(a, sz);
	PrintArray(a, sz);
}

void TestHeapSort()
{
	int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
	int sz = sizeof(a) / sizeof(a[0]);
	PrintArray(a, sz);
	HeapSort(a, sz);
	PrintArray(a, sz);
}

void TestQuickSort()
{
	int a[] = { 4,7,1,9,3,6,5,8,3,2,0 };
	int sz = sizeof(a) / sizeof(a[0]);
	PrintArray(a, sz);
	QuickSort(a, 0, sz - 1);
	PrintArray(a, sz);
}

void test()
{
	int a[] = { 5,5,3 };
	int ret = GetMidIndex(a, 0, 2);
	printf("%d", a[ret]);
}

void QuickSortNonR(int *a ,int begin, int end)
{
	ST st;
	STInit(&st);

	STPush(&st,end);
	STPush(&st, begin);

	while (!STEmpty(&st))
	{
		int left = STTop(&st);
		STPop(&st);
		int right = STTop(&st);
		STPop(&st);

		int keyi = PartSort3(a, left, right);

		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (left < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, left);
		}
	}

	STDestroy(&st);
}

TestQuickNonR()
{
	int a[] = { 3,2,4,6,5,7,8,1,9 };
	int sz = sizeof(a) / sizeof(a[0]);

	PrintArray(a, sz);
	QuickSortNonR(a, 0, sz - 1);
	PrintArray(a, sz);
}

int main()
{
	//TestInsertSort();
	//TestShellSort();
	//TestBubbleSort();
	//TestSelectSort();
	//TestHeapSort();
	//TestQuickSort();
	TestQuickNonR();
	//test();
}